﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgoFun
{
    public class PowerSet
    {
        public List<List<char>> GetPowerSet(List<char> list)
        {
            var result = new List<List<char>>();

            #region Logic

            int val = 1 << list.Count;
            Console.WriteLine("{0:00000000}", Convert.ToString(1, 2).PadLeft(8, '0'));
            Console.WriteLine("{0:00000000}", Convert.ToString(val, 2).PadLeft(8, '0'));


            for (int i = 0; i < (1 << list.Count); i++) // 1 << n == the n-th power of 2
            {
                var sublist = new List<char>();

                for (int j = 0; j < list.Count; j++) // analyze each bit in "i"
                {
                    if ((i & (1 << j)) != 0) // if the j-th bit of i is set...
                    {
                        sublist.Add(list[j]);// add the item to the current sublist
                    }
                }
                result.Add(sublist); // add the current sublist to the final result
            }

            #endregion

            return result;
        }


        //Linq version
        public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
        {
            return from m in Enumerable.Range(0, 1 << list.Count)
                   select
                       from i in Enumerable.Range(0, list.Count)
                       where (m & (1 << i)) != 0
                       select list[i];
        }

    }

}
